import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

class ListNode {
    int val;
   ListNode next;

    ListNode(int x) {
        val = x;
        next = null;
    }
}
public class DAY0320 {

    public boolean hasCycle(ListNode head) {
        Set<ListNode> set=new HashSet<ListNode>();
        while (head!=null){
            if(!set.add(head)){
                return true;
            }
            head=head.next;
        }
        return false;
    }

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        } else if (l2 == null) {
            return l1;
        } else if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }

    public ListNode removeElements(ListNode head, int val) {
        ListNode head1=new ListNode(0);
        head1.next=head;
        ListNode cur=head1;
        while(cur.next!=null){
            if(cur.next.val==val){
                cur.next=cur.next.next;
            }else {
                cur=cur.next;
            }
        }
        return head1.next;
    }


    public int specialArray(int[] nums) {
        Arrays.sort(nums);
        int n=nums.length;
        for (int i = 0,j=n-1; i <j; i++,j--) {
            int temp=nums[i];
            nums[i]=nums[j];
            nums[j]=temp;
        }
        for (int i = 1; i <=n ; i++) {
            if(nums[i-1]>=i&&(i==n||nums[i]<i)){
                return i;
            }
        }
        return -1;
    }

    public int[] twoSum(int[] numbers, int target) {
        for (int i = 0; i < numbers.length; ++i) {
            int low = i + 1, high = numbers.length - 1;
            while (low <= high) {
                int mid = (high - low) / 2 + low;
                if (numbers[mid] == target - numbers[i]) {
                    return new int[]{i + 1, mid + 1};
                } else if (numbers[mid] > target - numbers[i]) {
                    high = mid - 1;
                } else {
                    low = mid + 1;
                }
            }
        }
        return new int[]{-1, -1};
    }


}
